package SingleLinkedList;

import SingleLinkedList.Exception.IndexOutofException;

import java.util.List;

public class MySingleLinkedList<T>{
    //定义一个头指针
    Node head;
    //定义一个size来记录链表中的节点个数
    int size;

    //以内部类的形式定义节点
    class Node {
        T data;
        Node next;

        public Node(T data) {
            this.data = data;
        }

    }

    //头插法
    public void addFirst(T data) {
        Node newNode = new Node(data);
        newNode.next = head;
        this.head = newNode;
        this.size++;
    }

    //尾插法
    public void addLast(T data) {
        //需要判空
        if(this.size == 0) {
            addFirst(data);
            return;
        }

        //链表不为空的时候寻找最后一个节点
        Node cur = this.head;

        while(cur.next != null) {
            cur = cur.next;
        }

        Node newNode = new Node(data);
        cur.next = newNode;
        this.size ++;
    }

    //任意位置插入，第一个是数据节点为0号下标
    public void addIndex(int index,T data) {
        //判断下标是否合法
        if(index < 0 || index > size) {
            throw new IndexOutofException("下标不合法！");
        }

        //处理特殊情况
         if(index == 0) {
             addFirst(data);
             return;
         }

         if(index == size) {
             addLast(data);
             return;
         }

         //寻找下标为index的前驱节点
        //利用计数器
        int count = 0;
        Node cur = this.head;
        while(count < index - 1) {
            cur = cur.next;
            count++;
        }

        Node newNode = new Node(data);
        newNode.next = cur.next;
        cur.next = newNode;

        //链表中节点的数量自增
        this.size++;

    }

    //查看单链表是否包含关键字key
    public boolean contains(T key) {
        Node cur = head;
        while(cur != null) {
            assert key != null;
            if(key.equals(cur.data)) {
                return true;
            }

            cur = cur.next;
        }

        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(T key) {

          Node cur = this.head;
          //处理空链表
         if(cur == null) {
             return;
         }

         //查看头节点是否为key
          if(cur.data.equals(key)) {
              this.head = cur.next;
              this.size--;
              return;
          }
          //处理尾部节点
          while(!cur.next.data.equals(key)) {
              cur = cur.next;
          }

          //遍历到最后都没找到
          if(cur.next == null) {
              return;
          }

          //删除指定目标节点，并维护size变量
          cur.next = cur.next.next;
          this.size--;
    }

    //删除所有值为key的节点
    public void removeAllKey(T key) {
        if(head == null) {
            return;
        }

       //先删除后面的节点，再来关注前面的节点
        Node fast = head.next;
        Node slow = head;

        while(fast != null) {
            if(fast.data.equals(key)) {
                slow.next = fast.next;
                fast = fast.next;
            }else{
                fast = fast.next;
                slow = slow.next;
            }


        }

        //处理头部的节点
       if(head.data.equals(key)) {
           head = head.next;
       }

    }

    //得到单链表的长度
    public int size() {
        return this.size;
    }

    //清空整个单链表
    public void clear() {

    }

    //打印整个单链表
    public void display() {
        if(this.head == null) {
            System.out.println("链表为空");
            return;
        }

           Node cur = this.head;
           while(cur != null) {
               System.out.print(cur.data + " ");
               cur = cur.next;
           }
    }
}
